package arithmetic2.day03;

import java.util.Arrays;

/*
    堆排序：将数组看做依次对应的完全二叉树
    索引为i的节点左孩子为2*i+1,右孩子为2*i+2
 */
public class Demo01 {
    public static void main(String[] args) {
        int arr[] = new int[]{3, 6, 8, 3, 1, 2, 0};
        heapSort(arr, 0, arr.length - 1);
//        buildHeap(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    //堆排序
    public static void heapSort(int arr[], int start, int end) {
        int size = end - start + 1;
        //将数组变为大根堆
        buildHeap(arr, start, end);   // O(NlogN)
        //将第一个元素与最后一个元素交换
        swap(arr, 0, end);
        //持续调整堆
        for (int i = 0; i < arr.length - 1; i++) {  // O(N)
            heapify(arr, --size);    // O(logN)
            swap(arr, start, start + size - 1);
        }
    }

    //将数组变为大根堆
    public static void buildHeap(int arr[], int start, int end) {
        //将元素依次添加到堆中,构建大根堆
        for (int i = start; i <= end; i++) {        // O(N)
            heapInsert(arr, i);  // O(logN)
        }
    }

    //往堆中添加一个节点，当前节点与它的父节点比较，如果比父节点大，那么就交换,构建大根堆
    public static void heapInsert(int arr[], int cur) {
        while (cur > 0) {
            //求当前节点的父节点的索引
            int parent = (cur - 1) >> 1;
            //  当前节点小于父节就不用换了
            if (arr[parent] >= arr[cur]) {
                return;
            }
            //当前节点与父节点交换
            swap(arr, cur, parent);
            //改变当前节点索引，继续下一次比较
            cur = parent;
        }
    }

    //将数组中第一个元素放在适当的位置，使数组依然变为大根堆 O(logN)
    public static void heapify(int arr[], int size) {
        if (size > 1) {
            int index = 0;
            while (index < size) {
                //只有左子节点,并且左子节点大于当前节点
                if (2 * index + 1 < size && 2 * index + 2 >= size && arr[2 * index + 1] > arr[index]) {
                    swap(arr, index, 2 * index + 1);
                    index = 2 * index + 1;
                } else if (2 * index + 2 < size) { //有两个节点
                    //将两个子节点大的与当前交换
                    if (arr[2 * index + 1] > arr[2 * index + 2]) {
                        swap(arr, index, 2 * index + 1);
                        index = 2 * index + 1;
                    } else {
                        swap(arr, index, 2 * index + 2);
                        index = 2 * index + 2;
                    }
                } else {
                    return;
                }
            }
        }
    }

    //交换两个数
    public static void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
